package puzzle.projecteuler.p300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import astudy.tree.impl.SegmentTree;

public class Problem212A {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		long s = System.currentTimeMillis();
		List<Cuboid> cs = new ArrayList<Cuboid>();
		for (int i = 0; i < 50000; i ++) {
			cs.add(c(i));
		}
		System.out.println(volumn(cs));
		System.out.println((System.currentTimeMillis()-s) + " ms");
	}
	
	public static class Point {
		int x;
		int y;
		int z;
		
		public Point(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
		
		public String toString() {
			return "(" + x + "," + y + "," + z + ")";
		}
	}
	
	public static class Cuboid {
		Point p1;
		Point p2;
		
		public Cuboid(Point p1, Point p2) {
			this.p1 = p1;
			this.p2 = p2;
		}
		
		public String toString() {
			return "{" + p1 + "," + "(" + (p2.x-p1.x) + "," + (p2.y-p1.y) + "," + (p2.z-p1.z) + ")}";
		}
		
		public long volume() { 
			return (p2.x-p1.x)*(p2.y-p1.y)*(p2.z-p1.z);
		}
	}

	public static int[] s;
	static {
		s = new int[300000];
		for (int i = 0; i < 300000; i ++) {
			if (i < 55) {
				int k = i+1;
				s[i] = (100000*((1 - 2*k + 3*k*k*k)%10) + (3 - 3*k + 7*k*k*k)%1000000)%1000000;
			} else {
				s[i] = (s[i-24] + s[i-55])%1000000;
			}
		}
	}
	
	public static Cuboid c(int n) {
		
		int x, y, z;
		x = s[6*n]%10000;
		y = s[6*n+1]%10000;
		z = s[6*n+2]%10000;
		Point p1 = new Point(x, y, z);
		
		x += 1+(s[6*n+3]%399);
		y += 1+(s[6*n+4]%399);
		z += 1+(s[6*n+5]%399);
		Point p2 = new Point(x, y, z);
		
		return new Cuboid(p1, p2);
	}
	
	public static class Rectangle {
		int top;
		int left;
		int bottom;
		int right;
		
		public Rectangle(int left, int bottom, int right, int top) {
			this.top = top;
			this.left = left;
			this.bottom = bottom;
			this.right = right;
		}
		
		public String toString() {
			return "{top:" + top + ", left:" + left + ", bottom:" + bottom + ", right:" + right + "}";
		}
	}
	
	/**
	 * 计算一组矩形的面积
	 * @param rcs
	 * @return
	 */
	public static int area(List<Rectangle> rcs) {
	
		Set<Integer> txs = new HashSet<Integer>();
		Map<Integer, List<Rectangle>> map = new HashMap<Integer, List<Rectangle>>();
		for (Rectangle rc: rcs) {
			txs.add(rc.left);
			txs.add(rc.right);
			int key = rc.left;
			if (map.get(key) == null) {
				map.put(key, new ArrayList<Rectangle>());
			}
			map.get(key).add(rc);
			key = -rc.right-1;
			if (map.get(key) == null) {
				map.put(key, new ArrayList<Rectangle>());
			}
			map.get(key).add(rc);
		}
		Integer[] xs = txs.toArray(new Integer[txs.size()]);
		Arrays.sort(xs);

		SegmentTree yTree = new SegmentTree(0, 10400);

		int area = 0;
		for (int i = 0; i < xs.length-1; i ++) {
			
			int l = xs[i];
			int r = xs[i+1];
			if (map.get(l) != null) {
				for (Rectangle rc: map.get(l)) {
					yTree.insert(rc.bottom, rc.top);
				}
			}
			if (map.get(-l-1) != null) {
				for (Rectangle rc: map.get(-l-1)) {
					yTree.delete(rc.bottom, rc.top);
				}
			}
			area += (r-l)*yTree.length();
		}
		return area;
	}
	
	public static long volumn(List<Cuboid> cs) {

		Set<Integer> tzs = new HashSet<Integer>(); 
		for (Cuboid c: cs) {
			tzs.add(c.p1.z);
			tzs.add(c.p2.z);
		}
		Integer[] zs = tzs.toArray(new Integer[tzs.size()]);
		Arrays.sort(zs);


		long volumn = 0;
		for (int i = 0; i < zs.length-1; i ++) {
			int b = zs[i];
			int t = zs[i+1];
			List<Rectangle> rcs = new ArrayList<Rectangle>();
			for (Cuboid c: cs) {
				if (c.p1.z <= b && c.p2.z > b) {
					rcs.add(new Rectangle(c.p1.x, c.p1.y, c.p2.x, c.p2.y));
				}
			}
			volumn += (t-b)*area(rcs);
		}
		return volumn;
	}
}
